Méthodes de Monte Carlo

4. Contrôle : Approximation des stratégies optimales

4.1. Quelques rappels sur la méthode par itération des stratégies : GPI

Comme nous l'avons vu avec les méthodes de programmation dynamique, la méthode par itération des stratégies consiste à effectuer deux processus qui interagissent l'un avec l'autre:

• Un processus d'évaluation de stratégie courante
• Un processus d'amélioration de la stratégie en l'optimisant à l'aide de la fonction des valeurs d'actions.

Durant l'itération des stratégies, ces deux processus alternent l'un avec l'autre, l'un devant se terminer avant que l'autre ne commence. Le terme général utilisé pour décrire cette méthode est l'itération des stratégies généralisées (Genergalized Policy Iteration - GPI). Quasiment toutes les méthodes utilisées en apprentissage par renforcement sont décrites sur ce principe. Si les deux processus d'évaluation et d'amélioration se stabilisent, alors les résultats sont optimaux. Les équations d'optimalité de Bellman sont ainsi remplies.

Ces processus d'évaluation et d'amélioration dans le cadre de la méthode GPI peut être vue comme deux entités en rivalité et en coopération. Elles sont en rivalité dans le sens où elles tendent vers des directions opposées. En effet, le fait de rendre une stratégie optimale par rapport à sa fonction des valeurs d'actions a tendance à rendre cette fonction incorrecte sur la stratégie modifiée. Inversement, le fait de rendre la fonction des valeurs d'actions en accord avec la stratégie a tendance à faire perdre l'optimalité de la stratégie. Cependant, sur un temps assez long, les deux s'accordent sur une solution commune : la fonction des valeurs est optimale, ainsi que la stratégie.

4.2. Approximation de la stratégie optimale avec les méthodes de Monte Carlo

Voyons maintenant comment utiliser l'estimation de la fonction des valeurs des actions afin de trouver une stratégie optimale à l'aide des méthodes de Monte Carlo. L'idée est de suivre les étapes utilisées en programmation dynamique, basées sur l'idée d'itérations des stratégies GPI.

Considérons une version classique d'itération des stratégies avec la méthode de Monte Carlo. Dans cette méthode, les phases d'évaluation et d'amélioration des stratégies alternent les unes après les autres:

On peut montrer que si le nombre d'épisodes est très grand et que chaque épisode est généré avec l'hypothèse d'exploration des départs, alors les méthodes de Monte Carlo calculent les séquences ${q_{{\pi _k}}}$ de manière exacte, pour n'importe quelle séquence ${\pi _k}$.

L'amélioration des stratégie est réalisée en rendant la stratégie optimale par rapport à la fonction des valeurs des actions courante:

$${\pi _{k + 1}}\left( s \right) = \mathop {\arg \max }\limits_a {q_{{\pi _k}}}\left( {s,a} \right)$$

Idéalement il faudrait que l'évaluation de la stratégue se fasse un nombre infini de fois pour que cette méthode converge. Cependant, comme cela a déjà été fait avec les méthodes de programmation dynamique, il suffit de quelques pas de calcul pour s'approcher suffisamment de le solution. Et de manière extrême, il suffit d'alterner entre les phases d'évaluation et d'amélioration sur des pas unitaires. Avec les méthodes de Monte Carlo, il est naturel d'alterner ces calculs à chaque épisode.

Algorithme